#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
void HeapInsert(std::vector<int> &nums, int index) {
  if ((index <= 0) || (index >= nums.size())) {
    return;
  }
  int i = index;
  while ((i > 0) && (nums[i] > nums[(i - 1) / 2])) {
    swap(nums[i], nums[(i - 1) / 2]);
    i = (i - 1) / 2;
  }
}

void Heapify(std::vector<int> &nums, int index, int size) {
  if ((index < 0) || (index >= nums.size())) {
    return;
  }
  int left = 2 * index + 1;
  while (left < size) {
    if (left >= size) {
      break;
    }
    int begist = (nums[index] >= nums[left]) ? (index) : (left);
    int right = 2 * index + 2;
    if (right < size) {
      begist = (nums[begist] >= nums[right]) ? (begist) : (right);
    }
    if (begist == index) {
      break;
    }
    swap(nums[index], nums[begist]);
    index = begist;
    left = 2 * index + 1;
  }
}

void HeapSort(std::vector<int> &nums) {
  if (nums.size() <= 1) {
    return;
  }
  int size = nums.size();
  for (int i = 1; i < nums.size(); ++i) {
    HeapInsert(nums, i);
  }
  while (size > 0) {
    swap(nums[0], nums[size - 1]);
    --size;
    Heapify(nums, 0, size);
  }
}

vector<int> generateRandomArray(int max_size, int min_val, int max_val) {
  int size = rand() % max_size + 1; // 保证至少1个元素
  vector<int> arr(size);
  for (int i = 0; i < size; ++i) {
    arr[i] = rand() % (max_val - min_val + 1) + min_val;
  }
  return arr;
}

int main() {
  srand(time(0)); // 设置随机种子
  const int TEST_TIMES = 1000;
  const int MAX_SIZE = 1000;
  const int MIN_VAL = -1000;
  const int MAX_VAL = 1000;
  for (int i = 0; i < TEST_TIMES; ++i) {
    vector<int> arr = generateRandomArray(MAX_SIZE, MIN_VAL, MAX_VAL);
    vector<int> a = arr;
    std::sort(arr.begin(), arr.end());
    HeapSort(a);
    for (int i = 0; i < arr.size(); ++i) {
      if (a[i] != arr[i]) {
        cout << "Error: ";
        for (int i = 0; i < a.size(); ++i) {
          cout << a[i] << " ";
        }
        cout << endl;
        for (int i = 0; i < arr.size(); ++i) {
          cout << arr[i] << " ";
        }
        cout << endl;
        return 1;
      }
    }
  }
  cout << "所有 " << TEST_TIMES << " 次测试通过！" << endl;
  return 0;
}
